This invention relates to computer arithmetic devices, and more particularly to incrementers.
Many types of computing systems include an arithmetic-logic-unit (ALU). The ALU may be capable of performing sophisticated logical and arithmetic operations including multiply and divide. Special logic blocks may be added to speed up the more complex operations. A dedicated multiplier can rapidly perform multiply operations, while an integer divider can perform divide operations that otherwise would require thousands of clock cycles of the basic ALU.
These auxiliary math units may themselves contain several smaller blocks, such as shifters, adders, and leading-zero and other condition detectors. In particular, a divider may use an adder to increment a value such as for rounding a value from a floating point datapath. A general-purpose adder could be used for this sub-function.
Adders are often constructed from a one-bit adder cell known as a half-adder. FIG. 1 shows a prior-art half-adder cell. The one-bit input A of bit position (i) is added to a carry-in input CI from the next lower bit position (i−1).
Both a sum S and a carry-out CO to the next higher bit position (i+1) are generated by half-adder cell 10. The sum at position (i) of A and CI can be generated by exclusive-OR (XOR) gate 14, while the carry out CO to position (i+1) is generated by AND gate 12.
This is known as a half-adder cell because to perform a full add of two inputs X, Y, two such half-adder cells are needed for each bit position. One half-adder cell adds bit (i) of inputs X and Y to generate A(i), while the second half-adder cell adds the intermediate result A(i) to the carry CI(i) to generate the final sum.
While a full adder can be used to increment a binary number, a dedicated incrementer can be constructed. This incrementer can only add 1 or 0 to an input; it cannot add an arbitrary number as can a full adder. However, the amount of logic inside the incrementer can be less than the logic inside a full adder. A single half-adder cell is needed for each bit position in the incrementer, while two half-adder cells are required for each bit position in the full adder.
FIG. 2 shows a dedicated ripple-carry incrementer. Seven half-adder cells 10 are strung together to form a 7-bit incrementer. The carry-input CI to the lowest (least-significant bit or LSB) half-adder cell 10 is set to 1 to perform an increment. This LSB carry input may also be set to zero when no increment is desired.
The LSB half-adder cell 10 adds this lowest CI to the LSB of input A, A(0), to form sum bit S(0). The carry output of bit 0 is coupled to the carry input CI of the half-adder cell 10 adding the next higher bit, A(1). This second half-adder cell 10 generates sum S(1) and a carry out CI that is connected to the carry input CI of the third half-adder cell 10.
The carry output generated by each half-adder cell is applied to the carry input of the next higher half-adder cell. The final carry output CO(6) from bit 6 can be discarded, or it can signal on overflow when it is a 1.
Since the carries are propagated through an AND gate in each half-adder cell 10, the LSB carry bit may have to pass through seven AND gates to reach the final carry out of bit 6 in a worst-case delay path. This is known as a ripple carry since the carry signal ripples through all bits of the adder or incrementer.
In full adders, various techniques have been used to reduce this worst-case delay of the carry rippling through all the bits of the adder. For example, look-ahead logic can be used to generate an intermediate carry by looking at the binary-number inputs and carry into a group of bits.
What is desired is a look-ahead for an incrementer rather than for a full adder. An incrementer with a carry-lookahead is desired to reduce carry ripple delays in a fast incrementer. A pipelined incrementer is desired to further reduce delays that occur within a clock cycle.